package zhengqc.heap;

import zhengqc.list.ArrayList;

import java.util.Arrays;

public abstract class AbstractHeap<E> implements Heap<E> {
    protected ArrayList<E> data;
    /* 返回完全二叉树的数组中, 一个索引所表示的元素的父节点的索引 */
    protected int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index: 0 doesn't have parent");
        }
        return (index-1) / 2;
    }
    /* 返回完全二叉树的数组中, 一个索引所表示的元素的左孩子节点的索引 */
    protected int leftChild(int index) {
        return 2 * index + 1;
    }
    /* 返回完全二叉树的数组中, 一个索引所表示的元素的右孩子节点的索引 */
    protected int rightChild(int index) {
        return 2 * index + 2;
    }
    protected void siftUp(int index) {}
    protected void siftDown(int index) {}
    protected void heapify() {
        for (int i = parent(data.getSize()-1); i >= 0; --i) {
            siftDown(i);
        }
    }

    @Override /* 获取堆中元素数量 */
    public int getSize() {
        return this.data.getSize();
    }
    @Override /* 堆是否为空 */
    public boolean isEmpty() {
        return this.data.isEmpty();
    }
    @Override /* 查看堆中最小或最大的元素 */
    public E peek() {
        if (isEmpty()) {
            throw new IllegalArgumentException("the heap is empty.");
        }
        return data.getFirst();
    }
    @Override /* 清空堆 */
    public void clear() {
        this.data.clear();
    }
    @Override /* 取出堆中最小或最大的元素 */
    public E extract() {
        E element = peek();
        data.swap(0, data.getSize()-1);
        data.removeLast();
        siftDown(0);
        return element;
    }
    @Override /* 向堆中添加元素 */
    public void append(E element) {
        data.addLast(element);
        siftUp(data.getSize()-1);
    }
    @Override /* 取出堆中的最大或最小元素, 并替换为元素 element */
    public E replace(E element) {
        E temp = peek();
        data.setFirst(element);
        siftDown(0);
        return temp;
    }

    @Override
    public String toString() {
        return Arrays.toString(this.data.toArray());
    }

    @Override
    public E[] toArray() {
        E[] array = this.data.toArray();
        return array;
    }
}
